#include <stdio.h>
#include <stdbool.h>  // 用于bool类型（C99及以上支持）

// 快速幂取模：计算 (base^exponent) % mod，避免溢出
// 核心优化：通过二进制分解降低时间复杂度，同时每步取模防止溢出
long long fast_pow_mod(long long base, long long exponent, long long mod) {
    long long result = 1;
    base = base % mod;  // 先对底数取模，减少初始值大小
    while (exponent > 0) {
        // 若指数当前位为1，将结果与当前底数相乘后取模
        if (exponent & 1) {
            result = (result * base) % mod;
        }
        // 底数平方后取模，指数右移一位（相当于除以2）
        base = (base * base) % mod;
        exponent >>= 1;
    }
    return result;
}

// 对应Python的check函数：验证Miller-Rabin测试的条件
bool check(long long a, long long n) {
    long long x = n;
    long long p = n + 1;  // p = n+1（原Python中p = n+1，对应素性测试的n'=p-1）

    // 提取x中的所有因子2（将x转为奇数）
    while ((x & 1) == 0) {
        x >>= 1;  // x = x / 2
        // 计算 (a^x + 1) % p，若等于0则返回true
        long long val = (fast_pow_mod(a, x, p) + 1) % p;
        if (val == 0) {
            return true;
        }
    }

    // 最后验证 (a^x - 1) % p == 0
    long long final_val = (fast_pow_mod(a, x, p) - 1) % p;
    // 处理取模后为负数的情况（确保结果非负）
    if (final_val < 0) final_val += p;
    return final_val == 0;
}

// 对应Python的is_prim函数：判断n是否为素数
bool is_prim(long long n) {
    // 小数字直接判断
    if (n <= 4) {
        return (n == 2 || n == 3);
    }
    // 偶数直接返回false（大于2的偶数不可能是素数）
    if ((n & 1) == 0) {
        return false;
    }

    // 测试用的底数集合（与Python一致）
    long long a_list[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    int a_count = sizeof(a_list) / sizeof(a_list[0]);  // 计算数组长度

    // 对每个底数进行测试，全部通过则为素数
    for (int i = 0; i < a_count; i++) {
        long long a = a_list[i];
        // 若底数a >= n，跳过（避免无意义测试）
        if (a >= n) continue;
        if (!check(a, n - 1)) {
            return false;
        }
    }
    return true;
}

int main() {
    // 与Python原代码相同的测试用例
    printf("%s %lld\n", is_prim(10000) ? "true" : "false", 10000LL);
    printf("%s %lld\n", is_prim(911) ? "true" : "false", 911LL);
    printf("%s %lld\n", is_prim(561) ? "true" : "false", 561LL);
    printf("%s %lld\n", is_prim(341) ? "true" : "false", 341LL);

    return 0;
}